All possible full binary trees

Time: O(Nx4N/N(3/2)); Space: O(Nx4N/N(3/2)); medium

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

Example 1:

Input: N = 7

Output:

[
    {TreeNode} [0,0,0,None,None,0,0,None,None,0,0],
    {TreeNode} [0,0,0,None,None,0,0,0,0],
    {TreeNode} [0,0,0,0,0,0,0],
    {TreeNode} [0,0,0,0,0,None,None,None,None,0,0],
    {TreeNode} [0,0,0,0,0,None,None,0,0]
]

Constraints:

  • 1 <= N <= 20

[4]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

1. Binary Search [O(N4N/N(3/2)), O(N4N/N(3/2))]

[5]:

class Solution1(object):
    """
    Time: O(N*4^N/N^(3/2)) ~= sum of Catalan numbers from 1..N
    Space: O(N*4^N/N^(3/2)) ~= sum of Catalan numbers from 1..N
    """
    def __init__(self):
        self.__memo = {1: [TreeNode(0)]}

    def allPossibleFBT(self, N):
        """
        :type N: int
        :rtype: List[TreeNode]
        """
        if N % 2 == 0:
            return []

        if N not in self.__memo:
            result = []
            for i in range(N):
                for left in self.allPossibleFBT(i):
                    for right in self.allPossibleFBT(N-1-i):
                        node = TreeNode(0)
                        node.left = left
                        node.right = right
                        result.append(node)
            self.__memo[N] = result

        return self.__memo[N]

    def tree_to_list(self, tree):
        items = []
        queue = [tree]

        while queue:
            copy = queue[:]
            queue = []

            for item in copy:
                if item is None:
                    items.append(None)
                    queue.append(None)
                    queue.append(None)
                else:
                    items.append(item.val)
                    queue.append(item.left)
                    queue.append(item.right)

            if all((x is None for x in queue)):
                break

        return items

[6]:

s = Solution1()

N = 7
list_tree = s.allPossibleFBT(N)
# for tree in list_tree:
#     print(s.tree_to_list(tree))
assert(s.tree_to_list(list_tree[0])) == [0, 0, 0, None, None, 0, 0, None, None, None, None, None, None, 0, 0]
assert(s.tree_to_list(list_tree[1])) == [0, 0, 0, None, None, 0, 0, None, None, None, None, 0, 0, None, None]
assert(s.tree_to_list(list_tree[2])) == [0, 0, 0, 0, 0, 0, 0]
assert(s.tree_to_list(list_tree[3])) == [0, 0, 0, 0, 0, None, None, None, None, 0, 0, None, None, None, None]
assert(s.tree_to_list(list_tree[4])) == [0, 0, 0, 0, 0, None, None, 0, 0, None, None, None, None, None, None]